package 排序算法.选择排序;

import java.util.HashMap;

//直接选择排序
//基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
//简单选择排序是不稳定的排序,时间复杂度：T(n)=O(n2)。
public class Straight_Select_Sort {

    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        //sortA(a);
        sortB(a);
    }

    private static void sortA(int[] a){
        if (a == null || a.length == 0) {
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        for (int i=0;i<a.length;i++){
            int min=a[i];
            int n=i;//用来存放最小数的索引值
            for(int j=i+1;j<a.length;j++){//在剩下的数中查找最小的值
                if(a[j]<min){
                    min=a[j];
                    n=j;
                }
            }
            //交换位置
            a[n]=a[i];
            a[i]=min;
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void sortB(int[] a){
        if (a == null || a.length == 0) {
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }

        int minIndex=0;
        for(int i=0;i<a.length-1;i++){//比较n-1次
            minIndex=i;
            for (int j=i+1;j<a.length;j++){ //j代表索引值
                if(a[minIndex]>a[j]){
                    minIndex=j;
                }
            }
            if (minIndex!=i){ //说明存在更小的值
                swap(i,minIndex,a);
            }
        }

        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void swap(int i, int minIndex, int[] a) {
        int temp=a[i];
        a[i]=a[minIndex];
        a[minIndex]=temp;
    }
}
